package com.dy.树.验证二叉搜索树;

import com.dy.树.TreeNode;

import java.util.ArrayList;
import java.util.List;

/*
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {

        return  valid(root,Long.MIN_VALUE,Long.MAX_VALUE);

    }
    boolean valid(TreeNode root,long low,long high){
        if(root==null ) return true;

        if(root.val<=low ||root.val>=high) return false;



        return valid(root.left,low,root.val) && valid(root.right,root.val,high);
    }

//先中序遍历并存入list，然后在list中比较前后两位
    public boolean isValidBST2(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    public void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

}
